﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PcapMerger
{
    class PmInPlaceMergeSort
    {

        static void merge(List<IPmFrame> list, int offset , int sizei , int sizej)
        {
            IPmFrame temp;
            int ii = 0;
            int ji = sizei;
            int flength = sizei + sizej;

            for (int f = 0; f < (flength - 1); f++)
            {
                if (sizei == 0 || sizej == 0)
                    break;

                if (list[offset + ii].CompareTo(list[offset + ji]) < 0)
                {
                    ii++;
                    sizei--;
                }
                else
                {
                    temp = list[offset + ji];

                    for (int z = (ji - 1); z >= ii; z--)
                        list[offset + z + 1] = list[offset + z];
                    ii++;

                    list[offset + f] = temp;

                    ji++;
                    sizej--;
                }
            }
        }

        public static List<IPmFrame> MergeSort(List<IPmFrame> list, int offset = 0, int len = -1)
        {
            if (list == null)
                return null;

            if (len == -1)
                len = list.Count;

            int listsize, xsize;

            for (listsize = 1; listsize <= len; listsize *= 2)
            {
                for (int i = 0, j = listsize; (j + listsize) <= len; i += (listsize * 2), j += (listsize * 2))
                {
                    merge(list,i, listsize, listsize);
                }
            }

            listsize /= 2;

            xsize = len % listsize;
            if (xsize > 1)
                MergeSort(list,len - xsize, xsize);

            merge(list,0, listsize, xsize);

            return list;
        }
    }
}
